#include <iostream>
#define MAXN 10
#define INF 0x3f3f3f3f
using namespace std;

// dp[S][v] S表示当前访问过的点的集合, v表示当前所在的顶点, 那么dp就表示从v出发访问剩余的节点
// dp[V][0] = 0, dp[S][v] = min(dp[S | {u}][u] + d[u][v]);
int n;
int d[MAXN][MAXN], dp[1 << MAXN][MAXN];
void solve() {
    for (int S = 0; S < 1 << n; S++) {
        fill(dp[S], dp[S] + n, INF);
    }
    dp[(1 << n) - 1][0] = 0;
    for (int S = (1 << n) - 2; S >= 0; S--) {
        for (int v = 0; v < n; v++) {
            for (int u = 0; u < n; u++) {
                if (!(S >> u & 1)) {
                    dp[S][v] = min(dp[S][v], dp[S | 1 << u][u] + dp[v][u]);
                }
            }
        }
    }
    cout << dp[0][0] << endl;
}


// 从当前v出发, 前往未知的地方
// 小圈子到大圈子
int rec(int S, int v) {
    if (dp[S][v] > 0) return dp[S][v];
    if (S == (1 << n) - 1 && v == 0) return 0;
    int res = INF;
    for (int u = 0; u < n; u++) {
        if (!(S >> u & 1)) {
            res = min(res, rec(S | (1 << u), u) + dp[v][u]);
        }
    }
    return dp[S][v] = res;
}
